﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace DesignPatternDemoCApp.AlgorithmicDemo
{
    /// <summary>
    /// 顶点
    /// </summary>
    public class Vertex
    {
        /// <summary>
        /// 节点名称(A,B,C,D)
        /// </summary>
        public string name { get; set; }

        ///// <summary>
        ///// 最短路径长度(isMarked=true是才是最终的值)
        ///// </summary>
        //public int pathWeight { get; set; }

        /// <summary>
        /// 路径点名称集合(isMarked=true是才是最终的值)
        /// </summary>
        public List<string> pathNameList { get; set; }

        /// <summary>
        /// 节点是否已经出列(是否已经计算出最终的最短路径)
        /// </summary>
        public bool isMarked { get; set; }

        public Vertex(string name)
        {
            this.name = name;
            this.pathNameList = new List<string>();
        }

    }

    /// <summary>
    /// 无向图
    /// </summary>
    public class Graph
    {

        /// <summary>
        /// 顶点
        /// </summary>
        private List<Vertex> vertexs;

        /// <summary>
        /// 边
        /// </summary>
        private int[][] edges;


        public Graph(List<Vertex> vertexs, int[][] edges)
        {
            this.vertexs = vertexs;
            this.edges = edges;
        }

        /// <summary>
        /// 搜索各顶点最短路径
        /// </summary>
        public void search()
        {

            for (int i = 0; i < vertexs.Count - 1; i++)
            {
                //先取出第0行的最小路径(从起始顶点到其他访问过的点的路径最小值)
                int pathWeight = int.MaxValue;
                int col = 0;
                List<string> namePathList = new List<string>();
                for (int j = 0; j < vertexs.Count; j++)
                {
                    if (!vertexs[j].isMarked && edges[0][j] < pathWeight)
                    {
                        pathWeight = edges[0][j];
                        col = j;
                    }
                }
                //是否还存在有效的最短路径
                if (pathWeight > 0 && pathWeight < int.MaxValue)
                {
                    //顶点已经计算出最短路径
                    vertexs[col].isMarked = true;
                    if (vertexs[col].pathNameList.Count() == 0)
                    {
                        vertexs[col].pathNameList.Add(vertexs[col].name);
                    }
                    //打印当前路径
                    Console.WriteLine($@"{vertexs[0].name}->{vertexs[col].name}最短路径值为：{pathWeight},过程为：{vertexs[0].name}->{string.Join("->", vertexs[col].pathNameList)}");

                    //获取所有"未访问"的邻居
                    for (int j = 0; j < vertexs.Count; j++)
                    {
                        if (j == col)
                        {
                            //顶点本身，跳过
                            continue;
                        }
                        //到所有顶点的距离
                        int distance = edges[col][j];
                        if (distance < int.MaxValue)
                        {
                            //是邻居(有路径可达)
                            Vertex neighbor = vertexs[j];
                            if (!neighbor.isMarked)
                            {
                                //如果邻居没有访问过
                                if (distance + pathWeight < edges[0][j])
                                {
                                    edges[0][j] = distance + pathWeight;
                                    //记录过程点
                                    neighbor.pathNameList.Clear();
                                    neighbor.pathNameList.AddRange(vertexs[col].pathNameList);
                                    neighbor.pathNameList.Add(neighbor.name);
                                }
                            }
                        }
                    }


                }
            }
        }

        /// <summary>
        /// 打印图
        /// </summary>
        public void printGraph()
        {
            int verNums = vertexs.Count();
            for (int row = 0; row < verNums; row++)
            {
                for (int col = 0; col < verNums; col++)
                {
                    if (int.MaxValue == edges[row][col])
                    {
                        Console.Write("∞");
                        Console.Write("  ");
                        continue;
                    }
                    Console.Write(edges[row][col]);
                    Console.Write("  ");
                }
                Console.WriteLine();
            }
        }
    }

    /// <summary>
    /// 测试
    /// </summary>
    public class Test
    {

        public static void Main(string[] args)
        {
            List<Vertex> vertexs = new List<Vertex>();
            Vertex a = new Vertex("北京");
            Vertex b = new Vertex("上海");
            Vertex c = new Vertex("深圳");
            Vertex d = new Vertex("广州");
            Vertex e = new Vertex("成都");
            Vertex f = new Vertex("南充");
            vertexs.Add(a);
            vertexs.Add(b);
            vertexs.Add(c);
            vertexs.Add(d);
            vertexs.Add(e);
            vertexs.Add(f);

            //交错数组
            int[][] edges = {
                new int[6] { int.MaxValue, int.MaxValue, 10, int.MaxValue, 30, 100 },
                new int[6] { int.MaxValue, int.MaxValue, 5, int.MaxValue, int.MaxValue, int.MaxValue },
                new int[6] { int.MaxValue, int.MaxValue, int.MaxValue,50, int.MaxValue, int.MaxValue },
                new int[6] { int.MaxValue, int.MaxValue, int.MaxValue, int.MaxValue, int.MaxValue, 10 },
                new int[6] { int.MaxValue, int.MaxValue, int.MaxValue, 20, int.MaxValue, 60},
                new int[6] { int.MaxValue, int.MaxValue, int.MaxValue, int.MaxValue, int.MaxValue, int.MaxValue }};
            Graph graph = new Graph(vertexs, edges);
            Console.WriteLine("图的邻接矩阵:");
            graph.printGraph();
            Console.WriteLine($"Dijkstra算法,以{a.name}为起点的最短路径:");
            graph.search();
            Console.Read();
        }

    }

    class Program
    {
        static int[,] graph = new int[6, 6] { { 10000, 10000, 10, 10000, 30, 100 }, { 10000, 10000, 5, 10000, 10000, 10000 }, { 10000, 10000, 10000, 50, 10000, 10000 }, { 10000, 10000, 10000, 10000, 10000, 10 }, { 10000, 10000, 10000, 20, 10000, 60 }, { 10000, 10000, 10000, 10000, 10000, 10000 } };
        static int[] S = new int[6] { 0, 0, 0, 0, 0, 0 };//最短路径的顶点集合  
        static string[] mid = new string[6] { "", "", "", "", "", "" };//点的路线  
        public static int IsContain(int m)//判断元素是否在mst中  
        {
            int index = -1;
            for (int i = 1; i < 6; i++)
            {
                if (S[i] == m)
                {
                    index = i;
                }
            }
            return index;
        }
        /// <summary>  
        /// Dijkstrah实现最短路算法  
        /// </summary>  
        static void ShortestPathByDijkstra()
        {
            int min;
            int next;

            for (int f = 5; f > 0; f--)
            {
                //置为初始值  

                min = 1000;
                next = 0;//第一行最小的元素所在的列 next点  
                //找出第一行最小的列值  
                for (int j = 1; j < 6; j++)//循环第0行的列  
                {
                    if ((IsContain(j) == -1) && (graph[0, j] < min))//不在S中,找出第一行最小的元素所在的列  
                    {
                        min = graph[0, j];
                        next = j;
                    }
                }
                //将下一个点加入S  
                S[next] = next;
                //输出最短距离和路径  
                if (min == 1000)
                {
                    Console.WriteLine("V0到V{0}的最短路径为：无", next);
                }
                else
                {
                    Console.WriteLine("V0到V{0}的最短路径为：{1},路径为：V0{2}->V{0}", next, min, mid[next]);
                }
                // 重新初始0行所有列值  
                for (int j = 1; j < 6; j++)//循环第0行的列  
                {
                    if (IsContain(j) == -1)//初始化除包含在S中的  
                    {
                        if ((graph[next, j] + min) < graph[0, j])//如果小于原来的值就替换  
                        {
                            graph[0, j] = graph[next, j] + min;
                            mid[j] = mid[next] + "->V" + next;//记录过程点  
                        }
                    }
                }

            }

        }


        //static void Main(string[] args)
        //{
        //    ShortestPathByDijkstra();
        //    Console.Read();
        //}
    }
}

